package com.sailing.study.sort;

public class HeapSort {

    /**
     * {@link java.util.concurrent.PriorityBlockingQueue#siftUpComparable(int, Object, Object[])}
     * @param k
     * @param x
     * @param array
     * @param <T>
     */
    public static <T> void siftUpComparable(int k, T x, Object[] array) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = array[parent];
            if (key.compareTo((T) e) >= 0)
                break;
            array[k] = e;
            k = parent;
        }
        array[k] = key;
    }


    static class Node implements Comparable<Node>{
        int level;

        public Node(int level) {
            this.level = level;
        }

        @Override
        public int compareTo(Node o) {
            return this.level - o.level;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "level=" + level +
                    '}';
        }
    }

    public static void main(String[] args) {
        Node[] arrays = new Node[10];
        int cnt=0;
        for(int i=0;i<5;i++){
            int value = i+1;
            arrays[i] = new Node(value);
            System.out.println(arrays[i]);
            cnt++;
        }
        //
        int len = cnt;
        Node newNode = new Node(3);
        siftUpComparable(len, newNode, arrays);
        System.out.println("after sort :");
        for (Node node : arrays){
            System.out.println(node);
        }
    }
}
